package leetcode_500;

/**
 *@author 周杨
 *DiagonalTraverse_498  对角线遍历一个矩阵
 *describe:每次越界后换方向 AC 18%
 *2018年9月4日 下午7:06:17
 */
public class DiagonalTraverse_498 {
	public int[] findDiagonalOrder(int[][] matrix) {
		boolean up = true;
        if (matrix.length == 0) return new int[0];
        int[] res = new int[matrix.length * matrix[0].length];
        int i = 0;
        int j = 0;
        for (int k = 0; k < matrix.length * matrix[0].length; k++) {
            res[k] = matrix[i][j];
            if (up) {// 往右上走
                if ((i-1) >= 0 && (j+1) < matrix[0].length) {
                    i--;
                    j++;
                } else if ((j+1) < matrix[0].length) {
                    j++;
                    up = false;
                } else if ((i+1) < matrix.length) {
                    i++;
                    up = false;
                } else break;
            } else {// 往左下走
                if ((i+1) < matrix.length && (j-1) >= 0) {
                    i++;
                    j--;
                } else if ((i+1) < matrix.length) {
                    i++;
                    up = true;
                } else if ((j+1) < matrix[0].length) {
                    j++;
                    up = true;
                } else break;
            }
        }
        return res;
    }
}
